﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0130_HasPathSum : IAlgorithm
    {
        // 112. 路径总和

        // 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，
        // 这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
        // 叶子节点 是指没有子节点的节点。

        // 提示：
        //  树中节点的数目在范围[0, 5000] 内
        //  -1000 <= Node.val <= 1000
        //  -1000 <= targetSum <= 1000

        public void Test()
        {
            // 算法参数定义
            var root = new TreeNode(5,
                    new TreeNode(4,
                        new TreeNode(11,
                            new TreeNode(7),
                            new TreeNode(2)
                        )
                        ),
                    new TreeNode(8,
                        new TreeNode(13),
                        new TreeNode(4,
                            null,
                            new TreeNode(1)
                            )
                    )
                );
            // 算法执行与打印
            Console.WriteLine(HasPathSum(root, 22));
        }

        // 算法
        public bool HasPathSum(TreeNode root, int targetSum)
        {
            if (root == null)
            {
                return false;
            }
            if (root.left == null && root.right == null)
            {
                return targetSum == root.val;
            }
            return HasPathSum(root.left, targetSum - root.val) || HasPathSum(root.right, targetSum - root.val);
        }
    }
}
